This invention relates to a method and apparatus for displaying color image data. More particularly this invention relates to a computer which executes palette management software for servicing run-time demands for displaying multiple images simultaneously. Respective palettes for the images are combined in real time, while minimizing image degradation.
The use of color image data is a growing trend in personal and workstation computing. Until recent years, the hardware needed to achieve adequate image quality and image manipulation performance has been prohibitively expensive for the typical personal computer or workstation user. The introduction of less expensive color-mapped display subsystems has led to the development of many color image applications. Following is background information on color display subsystems, palette selection techniques, pixel mapping techniques and palette management techniques. The inventive subject matter herein is directed toward improved palette management techniques in a color-mapped display subsystem.
Color Display Subsystems
Color monitors are capable of displaying images at a specified resolution (e.g., 1280.times.1024; 1024.times.768). The 1280.times.1024 resolution monitor, for example, displays an image using 1280 rows of pixel elements by 1024 columns of pixel elements. The illuminated pixels are perceived in total as a color image. In a color monitor each pixel is composed of three smaller elements (called phosphors): one red, one green and one blue. The color of the pixel is determined by mixing the individual intensities of the red, green and blue (RGB) phosphors. In a computer environment, a digital signal drives the display to define the RGB intensities of each pixel. Each pixel is driven to define one of some finite number of colors as determined by an internal representation of an image within a computer's display hardware. Most display subsystems represent colors internally as 24-bit, 18-bit or 16-bit numbers. Often the bit pattern comprises subsets of the R, G and B components comprising the pixel color. For example, a 16-bit color often is represented by 5 bits of the red component, 6 bits of the green component and 5 bits of the blue component. An image occupying the entire display on a 16-bit color subsystem could require 1280.times.1024.times.16 bits of memory. A system storing an entire image in a buffer at maximum resolution is a full-color display subsystem. To achieve the high resolution of a full-color display subsystem, many megabytes of expensive VRAM are required.
Color-mapped display subsystems differ from full-color display subsystems by trading resolution to reduce memory needs. Specifically, resolution and memory requirements are decreased by restricting the image on a screen to a palette of a fixed number of colors. The conventional 8-bit color-mapped display subsystem uses a 256-color palette. For colors having 18-bit resolution the palette color-map table requires 4608 bits. For colors having 24-bit resolution the color-map table requires 6144 bits. A full color look-up table, however, requires space for 262,144 potential 18-bit colors or 16.7 million potential 24-bit colors.
To achieve high image quality or efficient image manipulation or substitution, a color-mapped subsystem requires effective palette selection and effective pixel mapping. If a palette is selected ineffectively or pixels are mapped ineffectively, poor image quality is observed.
Typically, palette selection is performed when an image is scanned into a computer system. Alternatively, a utility program converts a full-color image into an 8-bit color-mapped image. The color-mapped image is stored as a 256-color palette and an image bit-map of 8-bit indexes. Each index points to a color in the palette. When the image is to be displayed, the palette is loaded into a color-map table hardwired or integral to a video processor. The image bit-map then is output with each stored index value pointing to a color to be generated at the corresponding pixel.
Following are background sections on palette selection techniques and pixel mapping techniques. Thereafter, the palette management problem is defined.
Palette Selection Techniques
Given a picture with potentially millions of colors in it, how does one select and distribute a color map of 256 colors that are representative of the original image so that it looks "right" when viewed only with those colors in the color map. According to one common method, histogram clustering, it is assumed that the most significant colors will tend to cluster together when their lower order bits are truncated. A histogram of these reduced colors shows occurrences of the reduced colors. The 256 colors with the highest histogram values are taken as a representation of the colors in the image.
A more effective approach is vector quantization. According to vector quantization, palette selection is a data compression problem. The potentially millions of colors in the original picture are compressed to a representative set of 256 colors. Vector quantization is described generally in "Vector Quantization;" by Robert M. Gray, IEEE ASSP Magazine, April 1984. Vector Quantization as applied to image compression is described in "A New Vector Quantization Clustering Algorithm" by William H. Equitz, IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. 37, No. 10, October 1989. Vector Quantization as applied specifically to palette selection is described in (1) "A New Approach to Palette Selection for Color Images;" by Balasubramanian et al.; Journal of Imaging Technology, Vol. 17, No. 6, December 1991; and (2) "Color Quantization of Images;" by Orchard, et al.; IEEE Transactions on Signal Processing, Vol. 39, No. 12, December 1991. According to the vector quantization methods, an RGB image is analyzed as a set of 3-dimensional vectors (each vector representing a pixel comprising 3 phosphors--red, green and blue). Palette selection then is the vector quantization problem of choosing an optimal 8-bit codebook of 256 vectors which effectively compresses a given image' s potentially millions of colors down to 256 colors.
Equitz describes the generalized Lloyd algorithm of Linde, Buzo and Gray (also referred to as the LBG algorithm) for defining a codebook based on a set of training vectors (e.g., an initial set of pixel colors forming the color image). A starting codebook is selected, then each training vector (pixel color) is assigned its best fit based on a distortion measure. Next, for a given subset of vectors assigned to a code, the code is modified to minimize the distortion error among the vectors assigned to it. Iterations occur of assigning vectors based on fit and modifying the vectors to minimize error. A weakness of Lloyd's algorithm is that the selection of the initial codebook impacts the final result. Equitz proposes a pairwise nearest neighbor (PNN) algorithm to select the initial codebook, or alternatively, as a substitute for Lloyd's algorithm.
Equitz describes a full search version and an alternative fast search version of PNN clustering. Pairs of clusters are progressively merged based on minimizing weighted distance between cluster centroids. The full search PNN algorithm begins with a separate cluster for each vector in the image and merges two clusters at a time until the desired size vector codebook is achieved. For the fast-search version Equitz uses a data structure known as a K-d tree to reduce the scope of searching to O(log N) choices by subdividing the training set into "neighborhoods" and only considering merging vector pairs having centroids in the same neighborhood.
Balasubramanian et al. describe an application of Equitz's clustering vector quantization technique for palette selection. Initial image colors form a training set of sample vectors. Pairwise nearest neighbor (PNN) clustering of the initial sample vectors then is performed until the number of vectors equals the desired number of output codewords. Cluster centroids are chosen to be output centroids. Clusters are merged to minimize means squared error between vectors. PNN searches are implemented using K-dimensional trees. A prequantization step partitions RGB space into cubes. Centroids of colors in each cube are treated as the sample vectors. Image-dependent activity criteria determine the size of the cubes and weight intercluster distances to improve visual quality.
Orchard et al. describe a binary tree algorithm for partitioning clusters. Total squared-error, weighted total squared-error and erosion-based weighting are criteria applied for improving quantization. A gamma-based corrected coordinate system is used for computation, and L,a,b and L,u,v coordinate systems are proposed as alternative coordinate systems.
An alternative to the recursive bipartitioning methods of Equitz, Balasubramanian et al., and Orchard et al., is proposed in "Color Quantization by Dynamic Programming and Principal Analysis;" Xiaolin Wu, ACM Transactions on Graphics, Vol. 11, No. 4, October 1992. Wu proposes partitioning based on halfplanes set normal to a principal axis along which color points have maximum variance. Quantization is carried out in L*u*v space.
Pixel Mapping Techniques
Once a palette is selected, the pixels forming an image are mapped to the palette. Each pixel value of the original image is compared to the palette colors. An 8-bit index to a color in the palette closest to the original color is assigned to each pixel. By using 8-bit values for each pixel rather than 24 bits or 18 bits, the image consumes approximately one-third the memory of a full-color display subsystem.
Selection of one of the 256 colors in the palette is referred to as pixel mapping. In "Color Quantization of Images;" IEEE Transactions on Signal Processing, Vol. 39, No. 12, December 1991; Orchard et al. describe pixel mapping techniques for improving image quality. According to an "ordered dithering" technique, a pseudo-random noise pattern is added to blocks of pixels before quantizing them. According to an "error diffusion" technique, the image is quantized to have an average value substantially equal to the average value of the true image. In effect, these techniques allow a larger total squared error so that average color of the displayed and original images can be closely matched.
The Palette Management Problem
The problem of how to deal flexibly with color-mapped images has limited the potential of imaging applications on 8-bit display subsystems. (By 8-bit display subsystem, it is meant color-mapped display subsystems using an 8-bit index into a k-color palette (e.g., 256-color) of j-bit colors (e.g., 18-bit color resolution, 24-bit color resolution). For example, the task of simultaneously displaying two images with different palettes on an 8-bit display subsystem is so formidable that most applications and user interfaces do not allow such capability. Conventional applications displaying two images use the palette from one image to display the other. The image quality of the other image typically suffers from unacceptable levels of distortion. Accordingly, there is a need for a technology which effectively manages palettes from multiple images to enable simultaneous display of a plurality of minimally-distorted color quantized images.